/*************************************************************
 * 
 * CopyRight(c)2007, http://www.moorwind.com/
 * email:ezhung@gmail.com
 * for free, but a email permission would be nice
 * 
 ************************************************************/
package kono.utils
{
	//使用循环数组维护队列，  Queue built on a Circular-Array 
	public class ArrayedQueue
	{
		//队列数据， data of the queue
		private var data:Array;
		
		//队列数据的数量， total number of the items in the queue
		private var manyItems:uint;
		
		//指向队首， pointing to the head of the queue
		private var front:uint;
		
		//指向队尾， pointing to the tail of the queue
		private var rear:uint;
		
		public function ArrayedQueue(capacity:uint)
		{
			manyItems = 0;
			data = new Array(capacity);
		}
		
		//增加数据到队列中， add the given item into the queue
		public function enqueue(item:*):void
		{
			if(manyItems == data.length)
			{
				ensureCapacity(2*manyItems + 1);
			}			
			if(manyItems == 0)
			{
				front = rear = 0;
			}			
			else
			{
				rear = nextIndex(rear);
			}
			
			data[rear] = item;
			manyItems++ ;
		}
		
		//出队， get the first item in the queue and than remove it from the queue
		public function dequeue():*
		{
			var answer:*;
			if(manyItems == 0)
			{
				return null;
			}
			answer = data[front];
			front = nextIndex(front);
			manyItems--;
			return answer;
		} 
		
		//返回队首元素， get the first item
		public function peek():*
		{
			return data[front];
		}
		
		//得到队列容量， get the capacity of the queue
		public function get capacity():uint
		{
			return data.length;
		}
		
		//得到队列元素数量， get total number of the queue
		public function get size():uint
		{
			return manyItems;
		}
		
		//队列是否为空， check if the queue is empty
		public function isEmpty():Boolean
		{
			return (manyItems == 0);
		}
		
		//增加队列容量， enlarge the capacity of the queue
		public function ensureCapacity(capacity:uint):void
		{
			var biggerArray:Array;
			var i:uint, n1:uint, n2:uint;
			
			if(data.length >= capacity) return;
			else if(manyItems == 0) data = new Array(capacity);
			else if(front <= rear)
			{
				biggerArray = new Array(capacity);
				for(i = 0; i < data.length; i++)
				{
					biggerArray[i] = data [i];
				}
				data = biggerArray;				
			}
			else
			{
				biggerArray = new Array(capacity);
				n1 = data.length - front;
				n2 = rear + 1;
				for(i = front; i < data.length; i++)
				{
					biggerArray[i - front] = data [i];
				}
				for(i = 0; i < n2; i++)
				{
					biggerArray[n1 + i] = data [i];
				}
				front = 0;
				rear = manyItems - 1;
				data = biggerArray;
			}
		}
		
		public function toString():String
		{
			return "[ArrayedQueue, size=" + data.length + "]";
		}
		
		private function nextIndex(i:uint):uint
		{
			if(++i == data.length) return 0;
			else return i
		}
	}
}